package class51To60;

import java.util.ArrayList;
import java.util.Arrays;

public class CreateGraph {


    public static int MAX_N = 105;

    // 邻接矩阵
    public static int[][] graph1 = new int[MAX_N][MAX_N];

    // 邻接表
    // 不带权
    // public static ArrayList<ArrayList<Integer>> graph2 = new ArrayList<>();
    // 带权
    public static ArrayList<ArrayList<int[]>> graph2 = new ArrayList<>();

    // 链式前向星

    //边的数量，无向图*2
    public static int MAX_M = MAX_N * 2 + 1;

    public static int[] head = new int[MAX_N];

    public static int[] next = new int[MAX_M];

    public static int[] to = new int[MAX_M];

    public static int[] weight = new int[MAX_M];

    public static int cnt;

    /**
     * @param n 点的数量
     */
    public static void build(int n) {
        // 邻接矩阵初始化
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                graph1[i][j] = Integer.MAX_VALUE;
            }
        }
        // 邻接表初始化
        graph2.clear();
        for (int i = 0; i <= n; i++) {
            graph2.add(new ArrayList<>());
        }
        // 链式前向星初始化
        cnt = 1;
        Arrays.fill(head, 0, n + 1, 0);
    }

    // 链式前向星加边
    public static void addEdge(int u, int v, int w) {
        next[cnt] = head[u];
        to[cnt] = v;
        weight[cnt] = w;
        head[u] = cnt++;
    }

    // 带权有向图
    public static void directGraph(int[][] edges) {
        // 邻接矩阵加边
        for (int[] edge : edges) {
            graph1[edge[0]][edge[1]] = edge[2];
        }
        // 邻接表加边
        for (int[] edge : edges) {
            graph2.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        // 链式前向星加边
        for (int[] edge : edges) {
            addEdge(edge[0], edge[1], edge[2]);
        }
    }

    // 带权无向图
    public static void unDirectGraph(int[][] edges) {
        // 邻接矩阵加边
        for (int[] edge : edges) {
            graph1[edge[0]][edge[1]] = edge[2];
            graph1[edge[1]][edge[0]] = edge[2];
        }
        // 邻接表加边
        for (int[] edge : edges) {
            // 不带权
            // graph2.get(edge[0]).add(edge[1]);
            // graph2.get(edge[1]).add(edge[0]);
            graph2.get(edge[0]).add(new int[]{edge[1], edge[2]});
            graph2.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }
        // 链式前向星加边
        for (int[] edge : edges) {
            addEdge(edge[0], edge[1], edge[2]);
            addEdge(edge[1], edge[0], edge[2]);
        }
    }

    public static void traversal(int n) {
        System.out.println("邻接矩阵遍历 :");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(graph1[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("邻接表遍历 :");
        for (int i = 1; i <= n; i++) {
            System.out.print(i + "(邻居、边权) : ");
            for (int[] edge : graph2.get(i)) {
                System.out.print("(" + edge[0] + "," + edge[1] + ") ");
            }
            System.out.println();
        }
        System.out.println("链式前向星遍历 :");
        for (int i = 1; i <= n; i++) {
            System.out.print(i + "(邻居、边权) : ");
            for (int ei = head[i]; ei > 0; ei = next[ei]) {
                System.out.print("(" + to[ei] + "," + weight[ei] + ") ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 理解了带权图的建立过程，也就理解了不带权图
        // 点的编号为1...n
        // 例子1自己画一下图，有向带权图，然后打印结果
        int n1 = 4;
        int[][] edges1 = {{1, 3, 6}, {4, 3, 4}, {2, 4, 2}, {1, 2, 7}, {2, 3, 5}, {3, 1, 1}};
        build(n1);
        directGraph(edges1);
        traversal(n1);
        System.out.println("==============================");
        // 例子2自己画一下图，无向带权图，然后打印结果
        int n2 = 5;
        int[][] edges2 = {{3, 5, 4}, {4, 1, 1}, {3, 4, 2}, {5, 2, 4}, {2, 3, 7}, {1, 5, 5}, {4, 2, 6}};
        build(n2);
        unDirectGraph(edges2);
        traversal(n2);
    }


}
